package com.复杂链表的复制;

import java.util.HashMap;

public class Solution {
	
    public RandomListNode Clone(RandomListNode pHead)
    {
        //1首先复制不管随机指针的链表
        HashMap<RandomListNode,RandomListNode>hm = new HashMap<RandomListNode,RandomListNode>();
        RandomListNode pNode=pHead;//依旧指向原来的链表头
        RandomListNode pCloneHead=null ,pCloneNode=null;
        if(pNode!=null){
            int val = pNode.label;
            pCloneHead = new  RandomListNode(val);
            pCloneHead.next=null;
            pCloneHead.random=null;
            pCloneNode = pCloneHead;
            hm.put(pNode,pCloneNode);//将每个节点都存入到hashmap中这样可以快速的查找
            pNode = pNode.next;
    
         }
        while(pNode!=null){
            int val = pNode.label;
            RandomListNode temp = new RandomListNode(val);
            temp.next=null;
            pCloneNode.next=temp;
            pCloneNode = pCloneNode.next;
            hm.put(pNode,pCloneNode);
            pNode = pNode.next;
        }
        //此时已经将单向链表复制完成了开始将随机指针开始赋值
        pNode = pHead;
        pCloneNode = pCloneHead;
        RandomListNode temp=null;
        while(pNode!=null){
            temp=pNode.random;
            pCloneNode.random = hm.get(temp);
            pNode=pNode.next;
            pCloneNode = pCloneNode.next;
        }
        return pCloneHead;
    }
}
